package tree.binarytree.sum;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 二叉树的链式存储
 */
public class BinaryTree {

    private TreeNode root = null;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public TreeNode getRoot() {
        return root;
    }

    /**
     * 构造方法
     *
     * @param root
     */
    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    public BinaryTree() {
    }

    /**
     * 树是否是空树
     *
     * @return
     */
    public boolean isEmpty() {
        return root == null;
    }

    // 树的高度
    public int height() {
        return height(root);
    }

    // 节点个数
    public int size() {
        return size(root);
    }

    /**
     * 树的高度
     *
     * @param subTree
     * @return
     */
    private int height(TreeNode subTree) {
        if (subTree == null)
            return 0;// 递归结束：空树高度为0
        else {
            int i = height(subTree.getLeftChild());
            int j = height(subTree.getRightChild());
            return (i < j) ? (j + 1) : (i + 1);
        }
    }

    /**
     * 树的大小
     *
     * @param subTree
     * @return
     */
    private int size(TreeNode subTree) {
        if (subTree == null) {
            return 0;
        } else {
            return 1 + size(subTree.getLeftChild())
                    + size(subTree.getRightChild());
        }
    }

    /**
     * 获取父结点
     *
     * @param element
     * @return
     */
    public TreeNode parent(TreeNode element) {
        return (root == null || root == element) ? null : parent(root, element);
    }

    public TreeNode parent(TreeNode subTree, TreeNode element) {
        if (subTree == null)
            return null;
        if (subTree.getLeftChild() == element
                || subTree.getRightChild() == element)
            // 返回父结点地址
            return subTree;
        TreeNode p;
        // 现在左子树中找，如果左子树中没有找到，才到右子树去找
        if ((p = parent(subTree.getLeftChild(), element)) != null)
            // 递归在左子树中搜索
            return p;
        else
            // 递归在右子树中搜索
            return parent(subTree.getRightChild(), element);
    }

    /**
     * 获取左孩子
     *
     * @param element
     * @return
     */
    public TreeNode getLeftChildNode(TreeNode element) {
        return (element != null) ? element.getLeftChild() : null;
    }

    /**
     * 获取右孩子
     *
     * @param element
     * @return
     */
    public TreeNode getRightChildNode(TreeNode element) {
        return (element != null) ? element.getRightChild() : null;
    }

    /**
     * 销毁树
     * <p>
     * 在释放某个结点时，该结点的左右子树都已经释放，所以应该采用后续遍历，当访问某个结点时将该结点的存储空间释放
     *
     * @param subTree
     */
    public void destroy(TreeNode subTree) {
        // 删除根为subTree的子树
        if (subTree != null) {
            // 删除左子树
            destroy(subTree.getLeftChild());
            // 删除右子树
            destroy(subTree.getRightChild());
            // 删除根结点
            subTree = null;
        }
    }

    /**
     * 简单遍历树
     *
     * @param subTree
     */
    public void traverse(TreeNode subTree) {
        if (subTree == null) {
            return;
        }
        visted(subTree);
        if (subTree.getLeftChild() != null) {
            traverse(subTree.getLeftChild());
        }
        if (subTree.getRightChild() != null) {
            traverse(subTree.getRightChild());
        }
    }

    /**
     * 输出节点信息
     *
     * @param subTree
     */
    public void visted(TreeNode subTree) {
        if (subTree == null) {
            return;
        }
        if (subTree.isVisted()) {
            //已输出
            return;
        }
        subTree.setVisted(true);
        System.out.print(subTree.getData() + " ");
    }

    /**
     * 是否存在两个数的和为sum
     *
     * @param subTree 树
     * @param sum     和
     * @return
     */
    public boolean isHaveTwoNodeDateForSum(TreeNode subTree, final Integer sum) {
        boolean result = false;
        Set<Integer> set = new HashSet<>();
        if (subTree == null || sum == null) {
            return result;
        }

        //TODO


        return result;
    }


    /**
     * 二叉树的节点数据结构
     */
    static class TreeNode {
        /**
         * 唯一标示
         */
        private Integer data = null;
        private boolean visted = false;
        private TreeNode leftChild = null;
        private TreeNode rightChild = null;

        public TreeNode() {
        }

        public TreeNode(Integer data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public boolean isVisted() {
            return visted;
        }

        public void setVisted(boolean visted) {
            this.visted = visted;
        }

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

    }
}